import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yang
 * Date: 2022-07-21
 * Time: 13:06
 */
public class MergeSort {
    private static void merge(int start, int end, int[] array){
        if(start >= end)return;
        int mid = start+end>>1;
        merge(start,mid,array);
        merge(mid+1,end,array);

        int s1 = start;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = end;

        int[] tmp = new int[end - start + 1];
        int index = 0;
        while(s1 <= e1 && s2 <= e2){
            if(array[s1] <= array[s2])tmp[index++] = array[s1++];
            else tmp[index++] = array[s2++];
        }
        while(s1 <= e1){
            tmp[index++] = array[s1++];
        }
        while( s2 <= e2){
            tmp[index++] = array[s2++];
        }
        index = start;
        for (int i = 0; i < tmp.length; i++) {
            array[index++] = tmp[i];
        }
    }

    public static void mergeSort(int[] array){
        merge(0,array.length-1,array);
    }

    public static void main(String[] args) {
        int[] array = {4,6,2,8,3,6,4,7,9,3,6,5,4,6,8,9,12,14,13};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }
}
